/**
//地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一
//格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但
//它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ 
//
// 
//
// 示例 1： 
//
// 输入：m = 2, n = 3, k = 1
//输出：3
// 
//
// 示例 2： 
//
// 输入：m = 3, n = 1, k = 0
//输出：1
// 
//
// 提示： 
//
// 
// 1 <= n,m <= 100 
// 0 <= k <= 20 
// 
// Related Topics 深度优先搜索 广度优先搜索 动态规划 👍 525 👎 0

*/

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

import java.util.ArrayDeque;
import java.util.Queue;

public class ID_Offer_13_JiQiRenDeYunDongFanWeiLcof {
public static void main(String[] args) {
Solution solution = new ID_Offer_13_JiQiRenDeYunDongFanWeiLcof().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int totalCount = 0;

    public int movingCount(int m, int n, int k) {

        if(m == 1 && m == n) return 1;
        if(k == 0) return 1;

        //是否看过
        boolean[][] visited = new boolean[m][n];

        //点坐标表示
        Point point = new Point(0, 0);
        //queue,BFS下一个需要遍历的节点
        Queue<Point> bfsQueue = new ArrayDeque<>();
        bfsQueue.add(point);
        //直到所有点都遍历结束
        while(bfsQueue.peek() != null){
            //每次可以走四个方向，上m-1下m+1左n-1右n+1
            Point nowPoint = bfsQueue.poll();

            int y = nowPoint.y;
            int x = nowPoint.x;
            if(visited[y][x] == true) continue;
            totalCount++;
            visited[y][x] = true;
            //往上走
            if(y - 1 >= 0 && !visited[y-1][x] && lessEqualK(y-1,x,k)){
                bfsQueue.add(new Point(y-1, x));
            }
            //往下走
            if(y + 1 < m && !visited[y + 1][x] && lessEqualK(y+1,x,k)){
                bfsQueue.add(new Point(y+1, x));
            }
            //往左走
            if(x - 1 >= 0 && !visited[y][x - 1] && lessEqualK(y,x-1,k)){
                bfsQueue.add(new Point(y, x - 1));
            }
            //往右走
            if(x + 1 < n && !visited[y][x + 1] && lessEqualK(y,x+1,k)){
                bfsQueue.add(new Point(y, x + 1));
            }
        }

        return totalCount;

    }



    public boolean lessEqualK(Integer y, Integer x, int k){

        int sum = 0;

        //方法一： 传统方法，分解charArray
//        char[] yChar = y.toString().toCharArray();
//        char[] xChar = x.toString().toCharArray();
//
//        for(char c : yChar){
//            sum += Integer.parseInt(String.valueOf(new char[]{c}));
//        }
//        for(char c : xChar){
//            sum += Integer.parseInt(String.valueOf(new char[]{c}));
//        }

        //方法二： 每次取余，便是每个位数值
        int iY = y;
        int iX = x;
        while(iY != 0){
            int digital = iY % 10;
            sum += digital;
            iY = iY / 10;
        }

        while(iX != 0){
            int digital = iX % 10;
            sum += digital;
            iX = iX / 10;
        }

        if(sum <=k){
            return true;
        }else{
            return false;
        }

    }

}

class Point {
    public int y; //属于哪一行
    public int x; //属于哪一列

    public Point(int y, int x){
        this.y = y;
        this.x = x;
    }
}
//leetcode submit region end(Prohibit modification and deletion)




}